/**
给定一个 没有重复 数字的序列，返回其所有可能的全排列。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
 */
/**
 * 【排列】 有序：仅仅顺序不同算作不同的结果；
 * 不需要index---有序
 * 需要used数组标记使用状态--- 一个排列结果的不能有重复元素
 * !used[i]==true上一层使用过，跳过，选剩余元素；一个分支上避免选到重复元素
 * 【终止条件】
 * path.length === nums.length
 * 
 */
var permute = function(nums) {
    const res= [];
    const path = [];
    const k = nums.length;
    const used = Array(k).fill(false);
    const backTrack = () => {
      if(path.length === k) {
        res.push(path.slice());
        return;
      }
      for(let i=0;i<k;i++) {
        if(used[i]==true)continue; //used[i]==true上一层使用过，跳过，选剩余元素；一个分支上避免选到重复元素
        path.push(nums[i]);
        used[i]=true;
        backTrack();
        used[i]=false;
        path.pop();
      }
    }
    backTrack()
    return res;
};
const nums = [1,2,3];
console.log('全排列',permute(nums));